package com.lw.leetcode.binary.b;

/**
 * 1283. 使结果不超过阈值的最小除数
 *
 * @Author liw
 * @Date 2021/6/12 15:43
 * @Version 1.0
 */
public class SmallestDivisor {

    public static void main(String[] args){
        SmallestDivisor test = new SmallestDivisor();

        // nums = [1,2,5,9], threshold = 6
//        int[] arr = {11,2,5,9};

        // nums = [2,3,5,7,11], threshold = 11
//        int[] arr = {2,3,5,7,11};

        // nums = [19], threshold = 5
        int[] arr = {19};

        int bestValue = test.smallestDivisor(arr, 5);
        System.out.println(bestValue);
    }

    public int smallestDivisor(int[] nums, int threshold) {
        int st = 1;
        int end = 0;
        for (int i : nums) {
            end = Math.max(i, end);
        }
        long min = Integer.MAX_VALUE;
        long c;
        int value = 0;

        while (st <= end) {
            int m = st + ((end - st) >> 1);
            long sum = getSum(nums, m);
            if (sum > threshold) {
                st = m + 1;
            } else {
                end = m - 1;
                c = threshold - sum;
                if (c < min || (c == min && value > m)) {
                    min = c;
                    value = m;
                }
            }
        }
        return value;
    }

    private long getSum(int[] arr, int value) {
        long sum = 0;
        for (int i : arr) {
            int j = i / value;
            if(j * value != i) {
                sum++;
            }
            sum += j;
        }
        return sum;
    }
}
